package offer;

import java.util.Stack;

/**
 * @Author Elephas
 * @Date 2022/3/19
 **/
@FunctionalInterface
public interface Tree2Str {
    String tree2str(TreeNode root);
}

class Tree2StrImpl1 implements Tree2Str{

    /**
     * 递归实现前序遍历
     * @param root
     * @return
     */
    @Override
    public String tree2str(TreeNode root) {
        StringBuilder ans = new StringBuilder();
        if(root == null){
            return "";
        }else {
            preOrderTraversal(root, ans);
            return ans.toString();
        }
    }
    private void preOrderTraversal(TreeNode root, StringBuilder ans){
        ans.append(root.val);
        if(root.left != null && root.right != null){
            ans.append('(');
            preOrderTraversal(root.left, ans);
            ans.append(')').append('(');
            preOrderTraversal(root.right, ans);
            ans.append(')');
        }else if(root.left != null){
            ans.append('(');
            preOrderTraversal(root.left, ans);
            ans.append(')');
        }else if(root.right != null){
            ans.append("()");
            ans.append('(');
            preOrderTraversal(root.right, ans);
            ans.append(')');
        }else{
            // do nothing
        }
    }
}

class Tree2StrImpl2 implements Tree2Str{

    @Override
    public String tree2str(TreeNode root) {
        if(root == null){
            return "";
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<String> braceStack = new Stack<>();
        Stack<String> rightBraceStack = new Stack<>();
        StringBuilder ans = new StringBuilder();
        ans.append(root.val);
        if(root.left != null && root.right != null){
            stack.push(root.right);
            stack.push(root.left);
        }else if(root.left != null){
            stack.push(root.left);
        }else if(root.right != null){
            stack.push(root.right);
        }

        while(!stack.isEmpty()){

            // 出栈后补括号

            TreeNode node = stack.pop();
            ans.append(braceStack.pop());
            ans.append(node.val);

            // 入栈前补括号
            if(node.left != null && node.right != null){
                ans.append("(");
                braceStack.push(")(");
                braceStack.push(")");
                stack.push(node.right);
                stack.push(node.left);
            }else if(node.left != null){
                ans.append("(");
                braceStack.push(")");
                stack.push(node.left);
            }else if(node.right != null){
                ans.append("(()");
                braceStack.push(")");
                stack.push(node.right);
            }

        }

        return ans.toString();
    }

}